using namespace std;
//二叉链表结点存储结构
template <class T>class BiNode
{
private:
    /* data */
public:
    T data;
    BiNode<T> *lch;
    BiNode<T> *rch;
    BiNode():lch(NULL),rch(NULL){};
};
//二叉排序树类的定义
template <class T>class BST
{
private:
    
public:
    BiNode<T> *Root;
    BST(T r[],int n);
    ~BST();
    BiNode<T>* Search(BiNode<T> *R,T key);
    void InsertBST(BiNode<T> *&R,BiNode<T> *s);
    void Delete(BiNode<T> *&R);
    bool DeleteBST(BiNode<T> *&R,T key);
    void DestoryBST(BiNode<T> *Tree);
};
//构造函数，r[]是待插入的元素数组，n是其个数
template <class T>
BST<T>::BST(T r[],int n)
{
    Root=NULL;
    for (int i = 0; i < n; i++)
    {
        BiNode<T> *s=new BiNode<T>;
        s->data=r[i];
        s->lch=s->rch=NULL;
        InsertBST(Root,s);
    }
}
template <class T>
BST<T>::~BST()
{
    DestoryBST(Root);
}
//R为二叉树结点，key为关键字
template <class T>
BiNode<T>* BST<T>::Search(BiNode<T> *R,T key)
{
    if(R==NULL)
        return NULL;//查找失败
    if(key==R->data)
        return R;
    else if(key<R->data)
        return Search(R->lch,key);
    else
        return Search(R->rch,key);
}
//R为二叉排序树的根节结点，s为待插入的新结点
template <class T>
void BST<T>::InsertBST(BiNode<T> *&R,BiNode<T> *s)
{
    if (R==NULL)
    {
        R=s;
    }
    else if (s->data<R->data)
    {
        InsertBST(R->lch,s);
    }
    else
    {
        InsertBST(R->rch,s);
    }
}
//R是二叉排序树根结点，key是关键字
template <class T>
bool BST<T>::DeleteBST(BiNode<T> *&R,T key)
{
    if (R==NULL)
    {
        return false;
    }
    else
    {
        if (key==R->data)
        {
            Delete(R);
            return true; 
        }
        else if (key<R->data)
        {
            return DeleteBST(R->lch,key);
        }
        else
        {
            return DeleteBST(R->rch,key);
        }
    }
}
//删除结点R
template <class T>
void BST<T>::Delete(BiNode<T> *&R)
{
    BiNode<T> *q,*s;
    if (R->lch==NULL)//只有右子树
    {
        q=R;
        R=R->rch;
        delete q;
    }
    else if (R->rch==NULL)//只有左子树
    {
        q=R;
        R=R->lch;
        delete q;
    }
    else
    {
        q=R;
        s=R->lch;
        while (s->rch!=NULL)
        {
            q=s;
            s=s->rch;
        }
        R->data=s->data;
        if (q!=R)
        {
            q->rch=s->lch;
        }
        else
        {
            R->lch=s->lch;
        }
        delete s;
    }
}
//销毁二叉树
template <class T>
void BST<T>::DestoryBST(BiNode<T> *Tree)
{
    while (Tree)
    {
        BiNode<T> *lch=Tree->lch;
        BiNode<T> *rch=Tree->rch;
        cout<<"删除结点"<<  Tree->data<<endl;
        delete Tree;
        Tree=NULL;
        if (lch)
        {
            DestoryBST(lch);
        }
        if (rch)
        {
            DestoryBST(rch);
        }
    }
}